package com.peng.sort.quick;

import java.util.Arrays;

/**
 * quick sort 02 : 荷兰国旗分法  3 part ( <= pivot  and =pivot   and  > pivot )
 */
public class QuickSort02 {

    public static void main(String[] args) {
        int[] arr = {3, 5, 1, 2, 3, 7, 9};
        quickSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr) {
        process(arr, 0, arr.length - 1);
    }

    private static void process(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int[] pivot = getPivot(arr, L, R);

        process(arr, L, pivot[0]-1);
        process(arr, pivot[1]+1, R);


    }

    private static int[] getPivot(int[] arr, int L, int R) {

        if (L > R) {
            return new int[]{-1, -1};
        }
        if (L == R) {
            return new int[]{L, R};
        }

        int less = L - 1;
        int more = R;
        int i = L;

        while (i < more) {
            if (arr[i] < arr[R]) {
                swap(arr, i++, ++less);
            } else if (arr[i] == arr[R]) {
                i++;
            } else {
                swap(arr, i, --more);
            }

        }

        swap(arr, more, R);

        return new int[]{less+1,more};


    }

    private static void swap(int[] arr, int i, int j) {
        if (i == j) return;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
